package array.prefixsum;

import java.util.HashMap;

public class LongestWPI {

    public int longestWPI(int[] hours) {
        int n = hours.length;
        int[] preSum = new int[n + 1];
        preSum[0] = 0;
        HashMap <Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + (hours[i - 1] > 8 ? 1 : -1);
            if (!map.containsKey(preSum[i])) {
                map.put(preSum[i], i);
            }

            // 现在想找 hours[0...i - 1]中大于0的子数组
            // 要根据 preSum[i] 的正负判断
            if (preSum[i] > 0) {
                // preSum[i] > 0，则 hours[0...i - 1]中一定有子数组大于0
                // 考虑到 preSum数组每两个相邻元素的差的绝对值都是1且j应该尽可能小。
                // 那么只要找到 preSum[j] == preSum[i] - 1, nums[j + 1 ... i] 就是一个表现良好的时间段
                if (map.containsKey(preSum[i] - 1)) {
                    int j = map.get(preSum[i] - 1);
                    res = Math.max(res, i - j);
                }
            }
        }
        return res;
    }
}
